<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>eliminateEquations</title>
<style type="text/css">
	body {background-color: white; color: black; font-family:sans-serif; font-size:medium;}
	a:link {color: #3300ff;}
	a:visited {color: #663399;}
	a:hover {color:#0099ff;}
	a:active {color: #0066cc;}
	a.button {text-decoration:none;}
	
	table.nav  {background-color: #dbddff;}
	table.body {margin-top:2ex; margin-bottom:2ex;}
	table.programlistingindent {margin-left:32px;}
	
	img { margin-bottom:0px; margin-top:0px;}
	tt {margin-left:0.5em; margin-right:0.5em; font-weight:lighter;}
	
	p {margin-top:0ex;}
	p.synopsis {margin-left:32px;}
	p.programlistingindent {margin-left:32px;}
	p.citetitle {margin-left:2em;}
	
	ul ul {list-style-type:square;}
	ul li p {margin-top:0ex; margin-bottom:.5ex; padding:0}
	ol li p {margin-top:0ex; margin-bottom:.5ex; padding:0}
	
	h1.reftitle {color:#a90000;}
	h1.reftitle {font-size:3.7ex; margin-top:0; margin-bottom:0; font-weight:bold}
	h1.title {color:black; font-size:4ex; margin-top:1ex; font-weight:bold}
	h2.title {color:#bd0000; margin-top:1ex; margin-bottom:.9ex; font-weight:bold; font-size:3ex}
	h3.title {color:#bd0000; margin-top:1ex; margin-bottom:.9ex; font-weight:bold; font-size:2.5ex}
	h4.title {color:#bd0000; margin-top:1ex; margin-bottom:.9ex; font-weight:bold; font-size:2ex}
	h2 {color:#bd0000; margin-top:1ex; margin-bottom:.9ex; font-weight:bold; font-size:2.5ex}
	h3 {color:#bd0000; margin-top:1ex; margin-bottom:.9ex; font-weight:bold; font-size:2ex} 
	
	pre.programlisting {margin-left:32px;}
	pre.synopsis {margin-left:32px;}
	
	
	.categorytitle {margin-top:8px; padding-top:0px;}
	.categorylist {background-color: #e1e6f2;}
 	</style>
</head>
<body>
<a name="top_of_page"></a><p style="font-size:1px;"></p>
<h1 class="reftitle">eliminateEquations</h1>
<h2>Purpose</h2>
<p>Transforms LP/QP/MPLP/MPQP to LPC/PLCP</p>
<h2>Syntax</h2>
<pre class="synopsis">problem.qp2lcp</pre>
<pre class="synopsis">qp2lcp(problem)</pre>
<h2>Description</h2>
<p></p>
        Transformation of LP, QP, MPLP, and MPQP to LCP/PLCP formulation.
        Consider the following MPQP format that is accepted by <tt>Opt</tt> class:
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp33.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp33.png"></p>
        which contains <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp1.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp1.png">inequality constrains and <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp2.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp2.png"> equality constraints and constraints on the
        parameter <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp3.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp3.png">. If there are lower and upper bounds on the variables <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp4.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp4.png"> present, i.e. 
        <tt>lb</tt> and <tt>ub</tt>, these can be merged to inequalities <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp5.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp5.png">.
        This format is not appropriate for transformation to LCP form because it contains
        equality constraints and the inequalities are not nonnegative.
        
        To get appropriate LCP representation, the equality constrains of the problem 
        <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp6.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp6.png"> are removed using <tt>eliminateEquations</tt> method
        of the <tt>Opt</tt> class. The intermediate form of the optimization problem is given as
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp34.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp34.png"></p>
        with <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp7.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp7.png"> as the non-basic variables that map to <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp8.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp8.png"> affinely.
        
               
        Problem <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp9.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp9.png"> can be transformed effectively when 
        considering the rank of the matrix <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp10.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp10.png">.
        If the rank of matrix <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp11.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp11.png"> is less than the number of inequalities in <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp12.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp12.png">, then
        vector <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp13.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp13.png"> can be expressed as a difference of two positive numbers, i.e.
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp35.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp35.png"></p>
        Using the substitution
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp36.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp36.png"></p>
        and putting back to <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp14.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp14.png"> we get
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp37.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp37.png"></p>        
        which is a form suitable for PLCP formulation.
        
        
        If the rank of matrix <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp15.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp15.png"> is greater or equal than the number of inequalities in <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp16.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp16.png">, 
        we can factorize the matrix <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp17.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp17.png"> rowwise
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp38.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp38.png"></p>
        where <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp18.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp18.png">, <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp19.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp19.png"> are index sets corresponding to rows from which submatrices are built. The factored system
        can be written as
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp39.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp39.png"></p>
        where the matrix <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp20.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp20.png"> form by rows in the set <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp21.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp21.png"> must be invertible.                
        Using this substitution the system <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp22.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp22.png"> can be rewritten in variable <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp23.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp23.png">
        
      <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp40.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp40.png"></p>
        which is suitable for PLCP formulation where
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp41.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp41.png"></p>
        
        The corresponding PLCP can be written as follows:       
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp42.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp42.png"></p>
        where the problem data are built from MPQP <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp24.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp24.png">
        
      <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp43.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp43.png"></p>

        Original solution to MPQP problem <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp25.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp25.png"> can be obtained 
        by affine map from the variables <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp26.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp26.png"> and <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp27.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp27.png"> to <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp28.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp28.png">. The matrices of the backward map are stored inside
        <tt>recover</tt> property of the <tt>Opt</tt> class as follows
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp44.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp44.png"></p>
        If the problem was formulated using YALMIP, it is possible that some variables are in the different order. The original
        order of variables is stored in <tt>problem.varOrder.requested_variables</tt> and the map to original variables is given by
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp45.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp45.png"></p>        
                
	
   <h2>Input Arguments</h2>
<table cellspacing="0" class="body" cellpadding="4" border="0" width="100%">
<colgroup>
<col width="31%">
<col width="69%">
</colgroup>
<tbody><tr valign="top">
<td><tt>problem</tt></td>
<td>
<p></p> LP/QP/MPLP/MPQP optimization problem given as <tt>Opt</tt> class. <p>
	    		Class: <tt>Opt</tt></p>
</td>
</tr></tbody>
</table>
<h2>Example(s)</h2>
<h3>Example 
				1</h3>Consider MPQP in the following form
        <p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp46.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp46.png"></p>
            with one decision variables <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp29.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp29.png"> and two parameters <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp30.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp30.png">, <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp31.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp31.png">.            
         Construct MPQP optimization problem <pre class="programlisting"> H = 1; </pre>
<pre class="programlisting"></pre>
<pre class="programlisting"> A = [-1; -1]; b = [0.2; 0.4]; pB = [-1, 1; 0.5, -1]; </pre>
<pre class="programlisting"></pre>
<pre class="programlisting"> lb = -1; ub = 1; </pre>
<pre class="programlisting"></pre>
<pre class="programlisting"> Ath = [1 0;-1 0;0 1;0 -1]; bth = [1;1;1;1]; </pre>
<pre class="programlisting"></pre>
<pre class="programlisting"> problem = Opt('H',H,'A',A,'b',b,'pB',pB,'lb',lb,'ub',ub,'Ath',Ath,'bth',bth) </pre>
<pre class="programlisting">-------------------------------------------------
Parametric quadratic program
	Num variables:                1
	Num inequality constraints:   2
	Num equality constraints:     0
	Num lower bounds              1
	Num upper bounds              1
	Num parameters:               2
	Solver:                     PLCP
-------------------------------------------------
</pre> Transform <tt>problem</tt> to PLCP form <pre class="programlisting"> problem.qp2lcp </pre>
<pre class="programlisting">-------------------------------------------------
Parametric linear complementarity problem
	Num variables:                7
	Num inequality constraints:   0
	Num equality constraints:     0
	Num parameters:               2
	Solver:                     PLCP
-------------------------------------------------
</pre> Solve the appropriate PLCP <pre class="programlisting"> solution = problem.solve </pre>
<pre class="programlisting">mpt_plcp: 3 regions

solution = 

        xopt: [1x1 PolyUnion]
    exitflag: 1
         how: 'ok'
       stats: [1x1 struct]

</pre> Plot the optimizer, for instance the variables <img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp32.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp32.png">. <pre class="programlisting"> solution.xopt.fplot('z') </pre>
<pre class="programlisting"></pre>
<p class="programlistingindent"><img src="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp_img_1.png" alt="../../../../../fig/mpt/modules/solvers/@Opt/qp2lcp_img_1.png" width="60%"></p>
<h2>References</h2>
<p class="citetitle">[1] 
	Stephen Boyd and Lieven Vandenberghe: Convex Optimization; Cambridge University Press
</p>
<p class="citetitle">[2] 
	Richard W. Cottle, Jong-Shi Pang, Richard E. Stone: Linear complementarity problem, Academic Press Inc. 1992
</p>
<h2>See Also</h2>
<a href="./solve.html">solve</a>, <a href="../mpt_call_lcp.html">mpt_call_lcp</a><p></p>
<table class="nav" summary="Navigation aid" border="0" width="100%" cellpadding="0" cellspacing="0"><tr valign="top">
<td align="left" width="20">
<a href="../../../../mpt.html" class="button">&#9664;</a>  </td>
<td align="left">mpt</td>
<td>  </td>
<td align="right">eliminateequations</td>
<td align="right" width="20"><a href="eliminateequations.html" class="button">&#9654;</a></td>
</tr></table>
<br><p>©  <b>2010-2013</b>     Colin Neil Jones: EPF Lausanne,    <a href="mailto:colin.jones@epfl.ch">colin.jones@epfl.ch</a></p>
<p>©  <b>2010-2013</b>     Martin Herceg: ETH Zurich,    <a href="mailto:herceg@control.ee.ethz.ch">herceg@control.ee.ethz.ch</a></p>
</body>
</html>
